[Coding040] DataStructure - Stack

栈及其相关知识

More coding records

Get the knowledge flowing and circulating! :)

目录

标题：栈

堆栈（stack）又称为栈或堆叠，是计算机科学中的一种抽象资料类型，只允许在有序的线性资料集合的一端（称为堆栈顶端，top）进行加入数据（push）和移除数据（pop）的运算。因而按照后进先出（LIFO, Last In First Out）的原理运作，堆栈常用一维数组或链接串列来实现。常与另一种有序的线性资料集合队列相提并论。

堆栈使用两种基本操作：推入（压栈，push）和弹出（弹栈，pop）：

• 推入：将资料放入堆栈顶端，堆栈顶端移到新放入的资料。

• 弹出：将堆栈顶端资料移除，堆栈顶端移到移除后的下一笔资料。

堆栈的基本特点：

• 先入后出，后入先出。

• 除头尾节点之外，每个元素有一个前驱，一个后继。

关于栈的出栈顺序

※ 卡特兰数

案例

Java中的栈操作

xxxxxxxxxx
50
1
import java.util.Stack;
2

3
public class StackTest {
4

5
    public static void main(String[] args) {
6
        // TODO Auto-generated method stub
7
        
8
        // 定义字符串s
9
        String s = "(){}[]";
10
        
11
        Stack<Character> stack = new Stack();
12
        
13
        // 字符串转换为字符数组
14
        char[] strArray = s.toCharArray();
15
        
16
        for (char c : strArray)
17
        {
18
            System.out.println(c);
19
        }
20
        
21
        for (char c : strArray)
22
        {
23
            stack.push(c);
24
        }
25

26
        
27
        System.out.println("============");
28
        
29
        // size(): 求栈内元素的数量
30
        System.out.println("stack.size(): " + stack.size());
31
        
32
        // pop(): 去除栈顶元素的同时，返回该栈顶元素
33
        System.out.println("stack.pop(): " + stack.pop());  
34
        System.out.println("stack.size(): " + stack.size());
35
        
36
        // peek(): 只返回栈顶元素
37
        System.out.println("stack.peek(): " + stack.peek());
38
        System.out.println("stack.pop(): " + stack.pop());
39
        System.out.println("stack.size(): " + stack.size());
40
        
41
        // push(): 单独push一个元素
42
        stack.push('#');
43
        
44
        // empty(): 判空
45
        while (!stack.empty())
46
        {
47
            System.out.print(stack.pop() + " ");
48
        }
49
    }
50
}

★ Java知识积累

xxxxxxxxxx
14
1
// 定义字符串s
2
String s = "(){}[]";
3

4
// 声明Stack，且栈内存放的是Character对象
5
Stack<Character> stack = new Stack();
6

7
// 字符串转换为字符数组
8
char[] strArray = s.toCharArray();
9

10
// for循环的第二种遍历方式
11
for (char c : strArray)
12
{
13
 System.out.println(c);
14
}

声明Stack：Stack<Character> stack = new Stack();

字符串转字符数组：char[] strArray = s.toCharArray();